package com.leetcode.problems060;


import java.util.ArrayList;
import java.util.List;

/**
 * https://leetcode-cn.com/problems/permutation-sequence/
 * @Date 2021/11/20 14:34
 * @Author ghery
 * @Version V1.0
 */
public class Solution {


    public String getPermutation(int n, int k) {
        List<String> ans = new ArrayList<>();
        boolean[] used = new boolean[n + 1];
        getPermutation(n,k,used,new StringBuilder(),ans);
        return ans.get(k - 1);
    }


    public void getPermutation(int n, int k,boolean[] used,StringBuilder res,List<String> ans) {
        if(res.length() == n){
            ans.add(res.toString());
            return;
        }
        for (int i = 1; i <= n; i++) {
            if(ans.size() >= k){
                return;
            }
            if(!used[i]){
                used[i] = true;
                res.append(i);
                getPermutation(n,k,used,res,ans);
                res.delete(res.length() - 1,res.length());
                used[i] = false;
            }
        }
    }


    public static void main(String[] args) {
        System.out.println(new Solution().getPermutation(3,1));
    }
}
